package 算法.NiuKe.JZ;

import 算法.NiuKe.TreeNode;

import java.util.Stack;

/**
 * @author:谢君臣
 * @Date:2021/4/139:06
 * @version:1.0
 * @function: 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
 * 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
 * 平衡二叉树（Balanced Binary Tree），
 * 具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
 */
public class JZ39 {
    public static void main(String[] args) {

    }
    public boolean IsBalanced_Solution(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root==null)
            return true;
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            int left = getDeep(pop.left);
            int right = getDeep(pop.right);
            if (Math.abs(left-right)>1) {
                return false;
            }else {
                if (pop.left!=null)
                    stack.push(pop.left);
                if (pop.right!=null)
                    stack.push(pop.right);
            }
        }
        return true;
    }
    private int getDeep(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root==null) {
            return 0;
        }
        int deep = 0,max = 0;
        while (!stack.isEmpty()||root!=null){
            while (root!=null) {
                stack.push(root);
                root = root.left;
                deep++;
            }
            max = Math.max(deep, max);
            if (!stack.isEmpty()) {
                root = stack.pop();
                deep--;
                if (root.right!=null){
                    root = root.right;
                    deep++;
                }else root = null;
            }
        }
        return max;
    }
}
